/*
https://leetcode.cn/problems/find-all-good-strings/solution/zhao-dao-suo-you-hao-zi-fu-chuan-by-leetcode-solut/
 */
import java.util.Arrays;

public class Solution1397 {

    int[] fail;
    int[][][] f;
    int[][] trans;
    int mod=1000000007;
    String s1,s2,evil;

    public int findGoodStrings(int n, String s1, String s2, String evil) {
        this.s1=s1;
        this.s2=s2;
        this.evil=evil;
        fail=new int[evil.length()];
        for (int i=1,j=0;i<evil.length();i++){
            while (j>0 && evil.charAt(i)!=evil.charAt(j)){
                j=fail[j-1];
            }
            if (evil.charAt(i)==evil.charAt(j)){
                j++;
            }
            fail[i]=j;
        }
        f=new int[n][evil.length()][4];
        for (int i=0;i<n;i++){
            for (int j=0;j<evil.length();j++){
                Arrays.fill(f[i][j],-1);
            }
        }
        trans=new int[evil.length()][26];
        for (int i=0;i<trans.length;i++){
            Arrays.fill(trans[i],-1);
        }
        return dfs(0,0,3);
    }

    private int dfs(int pos, int status, int bound) {
        if (status==evil.length()){
            return 0;
        }
        if (pos==s1.length()){
            return 1;
        }
        if (f[pos][status][bound]==-1){
            f[pos][status][bound]=0;
            char l=(bound&1)!=0?s1.charAt(pos):'a';
            char r=(bound&2)!=0?s2.charAt(pos):'z';
            for (char c=l;c<=r;c++){
                int next_status=getTrans(status,c);
                int next_bound=((bound&1)!=0?(c==s1.charAt(pos)?1:0):0)^((bound&2)!=0?(c==s2.charAt(pos)?1:0)<<1:0);
                f[pos][status][bound]+=dfs(pos+1,next_status,next_bound);
                f[pos][status][bound]%=mod;
            }
        }
        return f[pos][status][bound];
    }

    private int getTrans(int status, char c) {
        if (trans[status][c-'a']==-1){
            int k=status;
            while (status>0 && evil.charAt(status)!=c){
                status=fail[status-1];
            }
            if (evil.charAt(status)==c){
                status++;
            }
            trans[k][c-'a']=status;
            status=k;
        }
        return trans[status][c-'a'];
    }

    public static void main(String[] args) {
        System.out.println(new Solution1397().findGoodStrings(2,"aa","da","b"));
    }
}
